home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 4 / Apprentice-Release4.iso / Languages / Caml Light 0.7 / Caml Light 0.7 source / src / yacc / lr0.c < prev    next >
Text File  |  1995-06-01  |  10KB  |  599 lines
  1.  
  2. #include "defs.h"
  3.  
  4. extern short *itemset;
  5. extern short *itemsetend;
  6. extern unsigned *ruleset;
  7.  
  8. int nstates;
  9. core *first_state;
  10. shifts *first_shift;
  11. reductions *first_reduction;
  12.  
  13. int get_state();
  14. core *new_state();
  15.  
  16. static core **state_set;
  17. static core *this_state;
  18. static core *last_state;
  19. static shifts *last_shift;
  20. static reductions *last_reduction;
  21.  
  22. static int nshifts;
  23. static short *shift_symbol;
  24.  
  25. static short *redset;
  26. static short *shiftset;
  27.  
  28. static short **kernel_base;
  29. static short **kernel_end;
  30. static short *kernel_items;
  31.  
  32.  
  33. allocate_itemsets()
  34. {
  35.     register short *itemp;
  36.     register short *item_end;
  37.     register int symbol;
  38.     register int i;
  39.     register int count;
  40.     register int max;
  41.     register short *symbol_count;
  42.  
  43.     count = 0;
  44.     symbol_count = NEW2(nsyms, short);
  45.  
  46.     item_end = ritem + nitems;
  47.     for (itemp = ritem; itemp < item_end; itemp++)
  48.     {
  49.     symbol = *itemp;
  50.     if (symbol >= 0)
  51.     {
  52.         count++;
  53.         symbol_count[symbol]++;
  54.     }
  55.     }
  56.  
  57.     kernel_base = NEW2(nsyms, short *);
  58.     kernel_items = NEW2(count, short);
  59.  
  60.     count = 0;
  61.     max = 0;
  62.     for (i = 0; i < nsyms; i++)
  63.     {
  64.     kernel_base[i] = kernel_items + count;
  65.     count += symbol_count[i];
  66.     if (max < symbol_count[i])
  67.         max = symbol_count[i];
  68.     }
  69.  
  70.     shift_symbol = symbol_count;
  71.     kernel_end = NEW2(nsyms, short *);
  72. }
  73.  
  74.  
  75. allocate_storage()
  76. {
  77.     allocate_itemsets();
  78.     shiftset = NEW2(nsyms, short);
  79.     redset = NEW2(nrules + 1, short);
  80.     state_set = NEW2(nitems, core *);
  81. }
  82.  
  83.  
  84. append_states()
  85. {
  86.     register int i;
  87.     register int j;
  88.     register int symbol;
  89.  
  90. #ifdef    TRACE
  91.     fprintf(stderr, "Entering append_states()\n");
  92. #endif
  93.     for (i = 1; i < nshifts; i++)
  94.     {
  95.     symbol = shift_symbol[i];
  96.     j = i;
  97.     while (j > 0 && shift_symbol[j - 1] > symbol)
  98.     {
  99.         shift_symbol[j] = shift_symbol[j - 1];
  100.         j--;
  101.     }
  102.     shift_symbol[j] = symbol;
  103.     }
  104.  
  105.     for (i = 0; i < nshifts; i++)
  106.     {
  107.     symbol = shift_symbol[i];
  108.     shiftset[i] = get_state(symbol);
  109.     }
  110. }
  111.  
  112.  
  113. free_storage()
  114. {
  115.     FREE(shift_symbol);
  116.     FREE(redset);
  117.     FREE(shiftset);
  118.     FREE(kernel_base);
  119.     FREE(kernel_end);
  120.     FREE(kernel_items);
  121.     FREE(state_set);
  122. }
  123.  
  124.  
  125.  
  126. generate_states()
  127. {
  128.     allocate_storage();
  129.     itemset = NEW2(nitems, short);
  130.     ruleset = NEW2(WORDSIZE(nrules), unsigned);
  131.     set_first_derives();
  132.     initialize_states();
  133.  
  134.     while (this_state)
  135.     {
  136.     closure(this_state->items, this_state->nitems);
  137.     save_reductions();
  138.     new_itemsets();
  139.     append_states();
  140.  
  141.     if (nshifts > 0)
  142.         save_shifts();
  143.  
  144.     this_state = this_state->next;
  145.     }
  146.  
  147.     finalize_closure();
  148.     free_storage();
  149. }
  150.  
  151.  
  152.  
  153. int
  154. get_state(symbol)
  155. int symbol;
  156. {
  157.     register int key;
  158.     register short *isp1;
  159.     register short *isp2;
  160.     register short *iend;
  161.     register core *sp;
  162.     register int found;
  163.     register int n;
  164.  
  165. #ifdef    TRACE
  166.     fprintf(stderr, "Entering get_state(%d)\n", symbol);
  167. #endif
  168.  
  169.     isp1 = kernel_base[symbol];
  170.     iend = kernel_end[symbol];
  171.     n = iend - isp1;
  172.  
  173.     key = *isp1;
  174.     assert(0 <= key && key < nitems);
  175.     sp = state_set[key];
  176.     if (sp)
  177.     {
  178.     found = 0;
  179.     while (!found)
  180.     {
  181.         if (sp->nitems == n)
  182.         {
  183.         found = 1;
  184.         isp1 = kernel_base[symbol];
  185.         isp2 = sp->items;
  186.  
  187.         while (found && isp1 < iend)
  188.         {
  189.             if (*isp1++ != *isp2++)
  190.             found = 0;
  191.         }
  192.         }
  193.  
  194.         if (!found)
  195.         {
  196.         if (sp->link)
  197.         {
  198.             sp = sp->link;
  199.         }
  200.         else
  201.         {
  202.             sp = sp->link = new_state(symbol);
  203.             found = 1;
  204.         }
  205.         }
  206.     }
  207.     }
  208.     else
  209.     {
  210.     state_set[key] = sp = new_state(symbol);
  211.     }
  212.  
  213.     return (sp->number);
  214. }
  215.  
  216.  
  217.  
  218. initialize_states()
  219. {
  220.     register int i;
  221.     register short *start_derives;
  222.     register core *p;
  223.  
  224.     start_derives = derives[start_symbol];
  225.     for (i = 0; start_derives[i] >= 0; ++i)
  226.     continue;
  227.  
  228.     p = (core *) MALLOC(sizeof(core) + i*sizeof(short));
  229.     if (p == 0) no_space();
  230.  
  231.     p->next = 0;
  232.     p->link = 0;
  233.     p->number = 0;
  234.     p->accessing_symbol = 0;
  235.     p->nitems = i;
  236.  
  237.     for (i = 0;  start_derives[i] >= 0; ++i)
  238.     p->items[i] = rrhs[start_derives[i]];
  239.  
  240.     first_state = last_state = this_state = p;
  241.     nstates = 1;
  242. }
  243.  
  244.  
  245. new_itemsets()
  246. {
  247.     register int i;
  248.     register int shiftcount;
  249.     register short *isp;
  250.     register short *ksp;
  251.     register int symbol;
  252.  
  253.     for (i = 0; i < nsyms; i++)
  254.     kernel_end[i] = 0;
  255.  
  256.     shiftcount = 0;
  257.     isp = itemset;
  258.     while (isp < itemsetend)
  259.     {
  260.     i = *isp++;
  261.     symbol = ritem[i];
  262.     if (symbol > 0)
  263.     {
  264.         ksp = kernel_end[symbol];
  265.         if (!ksp)
  266.         {
  267.         shift_symbol[shiftcount++] = symbol;
  268.         ksp = kernel_base[symbol];
  269.         }
  270.  
  271.         *ksp++ = i + 1;
  272.         kernel_end[symbol] = ksp;
  273.     }
  274.     }
  275.  
  276.     nshifts = shiftcount;
  277. }
  278.  
  279.  
  280.  
  281. core *
  282. new_state(symbol)
  283. int symbol;
  284. {
  285.     register int n;
  286.     register core *p;
  287.     register short *isp1;
  288.     register short *isp2;
  289.     register short *iend;
  290.  
  291. #ifdef    TRACE
  292.     fprintf(stderr, "Entering new_state(%d)\n", symbol);
  293. #endif
  294.  
  295.     if (nstates >= MAXSHORT)
  296.     fatal("too many states");
  297.  
  298.     isp1 = kernel_base[symbol];
  299.     iend = kernel_end[symbol];
  300.     n = iend - isp1;
  301.  
  302.     p = (core *) allocate((unsigned) (sizeof(core) + (n - 1) * sizeof(short)));
  303.     p->accessing_symbol = symbol;
  304.     p->number = nstates;
  305.     p->nitems = n;
  306.  
  307.     isp2 = p->items;
  308.     while (isp1 < iend)
  309.     *isp2++ = *isp1++;
  310.  
  311.     last_state->next = p;
  312.     last_state = p;
  313.  
  314.     nstates++;
  315.  
  316.     return (p);
  317. }
  318.  
  319.  
  320. /* show_cores is used for debugging */
  321.  
  322. show_cores()
  323. {
  324.     core *p;
  325.     int i, j, k, n;
  326.     int itemno;
  327.  
  328.     k = 0;
  329.     for (p = first_state; p; ++k, p = p->next)
  330.     {
  331.     if (k) printf("\n");
  332.     printf("state %d, number = %d, accessing symbol = %s\n",
  333.         k, p->number, symbol_name[p->accessing_symbol]);
  334.     n = p->nitems;
  335.     for (i = 0; i < n; ++i)
  336.     {
  337.         itemno = p->items[i];
  338.         printf("%4d  ", itemno);
  339.         j = itemno;
  340.         while (ritem[j] >= 0) ++j;
  341.         printf("%s :", symbol_name[rlhs[-ritem[j]]]);
  342.         j = rrhs[-ritem[j]];
  343.         while (j < itemno)
  344.         printf(" %s", symbol_name[ritem[j++]]);
  345.         printf(" .");
  346.         while (ritem[j] >= 0)
  347.         printf(" %s", symbol_name[ritem[j++]]);
  348.         printf("\n");
  349.         fflush(stdout);
  350.     }
  351.     }
  352. }
  353.  
  354.  
  355. /* show_ritems is used for debugging */
  356.  
  357. show_ritems()
  358. {
  359.     int i;
  360.  
  361.     for (i = 0; i < nitems; ++i)
  362.     printf("ritem[%d] = %d\n", i, ritem[i]);
  363. }
  364.  
  365.  
  366. /* show_rrhs is used for debugging */
  367. show_rrhs()
  368. {
  369.     int i;
  370.  
  371.     for (i = 0; i < nrules; ++i)
  372.     printf("rrhs[%d] = %d\n", i, rrhs[i]);
  373. }
  374.  
  375.  
  376. /* show_shifts is used for debugging */
  377.  
  378. show_shifts()
  379. {
  380.     shifts *p;
  381.     int i, j, k;
  382.  
  383.     k = 0;
  384.     for (p = first_shift; p; ++k, p = p->next)
  385.     {
  386.     if (k) printf("\n");
  387.     printf("shift %d, number = %d, nshifts = %d\n", k, p->number,
  388.         p->nshifts);
  389.     j = p->nshifts;
  390.     for (i = 0; i < j; ++i)
  391.         printf("\t%d\n", p->shift[i]);
  392.     }
  393. }
  394.  
  395.  
  396. save_shifts()
  397. {
  398.     register shifts *p;
  399.     register short *sp1;
  400.     register short *sp2;
  401.     register short *send;
  402.  
  403.     p = (shifts *) allocate((unsigned) (sizeof(shifts) +
  404.             (nshifts - 1) * sizeof(short)));
  405.  
  406.     p->number = this_state->number;
  407.     p->nshifts = nshifts;
  408.  
  409.     sp1 = shiftset;
  410.     sp2 = p->shift;
  411.     send = shiftset + nshifts;
  412.  
  413.     while (sp1 < send)
  414.     *sp2++ = *sp1++;
  415.  
  416.     if (last_shift)
  417.     {
  418.     last_shift->next = p;
  419.     last_shift = p;
  420.     }
  421.     else
  422.     {
  423.     first_shift = p;
  424.     last_shift = p;
  425.     }
  426. }
  427.  
  428.  
  429.  
  430. save_reductions()
  431. {
  432.     register short *isp;
  433.     register short *rp1;
  434.     register short *rp2;
  435.     register int item;
  436.     register int count;
  437.     register reductions *p;
  438.     register short *rend;
  439.  
  440.     count = 0;
  441.     for (isp = itemset; isp < itemsetend; isp++)
  442.     {
  443.     item = ritem[*isp];
  444.     if (item < 0)
  445.     {
  446.         redset[count++] = -item;
  447.     }
  448.     }
  449.  
  450.     if (count)
  451.     {
  452.     p = (reductions *) allocate((unsigned) (sizeof(reductions) +
  453.                     (count - 1) * sizeof(short)));
  454.  
  455.     p->number = this_state->number;
  456.     p->nreds = count;
  457.  
  458.     rp1 = redset;
  459.     rp2 = p->rules;
  460.     rend = rp1 + count;
  461.  
  462.     while (rp1 < rend)
  463.         *rp2++ = *rp1++;
  464.  
  465.     if (last_reduction)
  466.     {
  467.         last_reduction->next = p;
  468.         last_reduction = p;
  469.     }
  470.     else
  471.     {
  472.         first_reduction = p;
  473.         last_reduction = p;
  474.     }
  475.     }
  476. }
  477.  
  478.  
  479. set_derives()
  480. {
  481.     register int i, k;
  482.     register int lhs;
  483.     register short *rules;
  484.  
  485.     derives = NEW2(nsyms, short *);
  486.     rules = NEW2(nvars + nrules, short);
  487.  
  488.     k = 0;
  489.     for (lhs = start_symbol; lhs < nsyms; lhs++)
  490.     {
  491.     derives[lhs] = rules + k;
  492.     for (i = 0; i < nrules; i++)
  493.     {
  494.         if (rlhs[i] == lhs)
  495.         {
  496.         rules[k] = i;
  497.         k++;
  498.         }
  499.     }
  500.     rules[k] = -1;
  501.     k++;
  502.     }
  503.  
  504. #ifdef    DEBUG
  505.     print_derives();
  506. #endif
  507. }
  508.  
  509. free_derives()
  510. {
  511.     FREE(derives[start_symbol]);
  512.     FREE(derives);
  513. }
  514.  
  515. #ifdef    DEBUG
  516. print_derives()
  517. {
  518.     register int i;
  519.     register short *sp;
  520.  
  521.     printf("\nDERIVES\n\n");
  522.  
  523.     for (i = start_symbol; i < nsyms; i++)
  524.     {
  525.     printf("%s derives ", symbol_name[i]);
  526.     for (sp = derives[i]; *sp >= 0; sp++)
  527.     {
  528.         printf("  %d", *sp);
  529.     }
  530.     putchar('\n');
  531.     }
  532.  
  533.     putchar('\n');
  534. }
  535. #endif
  536.  
  537.  
  538. set_nullable()
  539. {
  540.     register int i, j;
  541.     register int empty;
  542.     int done;
  543.  
  544.     nullable = MALLOC(nsyms);
  545.     if (nullable == 0) no_space();
  546.  
  547.     for (i = 0; i < nsyms; ++i)
  548.     nullable[i] = 0;
  549.  
  550.     done = 0;
  551.     while (!done)
  552.     {
  553.     done = 1;
  554.     for (i = 1; i < nitems; i++)
  555.     {
  556.         empty = 1;
  557.         while ((j = ritem[i]) >= 0)
  558.         {
  559.         if (!nullable[j])
  560.             empty = 0;
  561.         ++i;
  562.         }
  563.         if (empty)
  564.         {
  565.         j = rlhs[-j];
  566.         if (!nullable[j])
  567.         {
  568.             nullable[j] = 1;
  569.             done = 0;
  570.         }
  571.         }
  572.     }
  573.     }
  574.  
  575. #ifdef DEBUG
  576.     for (i = 0; i < nsyms; i++)
  577.     {
  578.     if (nullable[i])
  579.         printf("%s is nullable\n", symbol_name[i]);
  580.     else
  581.         printf("%s is not nullable\n", symbol_name[i]);
  582.     }
  583. #endif
  584. }
  585.  
  586.  
  587. free_nullable()
  588. {
  589.     FREE(nullable);
  590. }
  591.  
  592.  
  593. lr0()
  594. {
  595.     set_derives();
  596.     set_nullable();
  597.     generate_states();
  598. }
  599.